// 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
// 思路，回溯
// startIndex这个变量代表每轮遍历的起始点，防止组合重复
// 终止条件为path的长度为k，递归回退的时候，把path撤销，进入下一轮遍历
// 遍历优化：`k - path.length`,剩余还需要的元素个数,`n - (k - path.length) + 1`，最大的起始点位置，如果不满足，则无序往后变遍历
function combine(n, k) {
    let result = []
    let path = []
    function backtracking(startIndex) {
        if (path.length === k) {
            result.push([...path])
            return
        }
        /**
         * 最后一个n的索引是n
         * 剩余还需要的元素个数是 k - path.length
         * 最后一个可取的数字索引是 n -（k - path.length）+ 1
         */
        for (let i = startIndex; i <= n - (k - path.length) + 1; i++) {
            path.push(i)
            backtracking(i + 1)
            path.pop()   
        }
    }
    backtracking(1)
    return result
}

let n = 4, k = 3
console.log(combine(n, k))